This application is related to co-pending U.S. patent application Ser. No. 09/226,776 entitled Methods And Apparatus For Variable Length SDRAM Transfers filed on the same day, which is incorporated herein by reference.
1. Field of the Invention
The present invention relates generally to arbitration for access to a digital device and more particularly, to techniques for arbitrating multiple data transfer requests to optimize the operation of a computer system.
2. Description of the Related Art
Dynamic random access memory (DRAM) is used to provide a number of different functions in computers including: xe2x80x9cscratch padxe2x80x9d memory and video frame buffers. Synchronous dynamic random access memory (SDRAM) is a type of DRAM designed to deliver bursts of data at very high speed using automatic addressing, multiple page interleaving, and a synchronous (or clocked) interface. The SDRAM is typically monitored and managed by a SDRAM controller.
The SDRAM controller receives data transfer requests for memory access to the SDRAM. To establish the priority of the data transfer requestors, the SDRAM controller generally includes an arbiter. The arbiter receives information from the requestors to determine the type of data transfer requested, and then uses an arbitration scheme to assign a priority to each of the requesters. The SDRAM controller then grants memory access to the SDRAM based on the priority established by the arbiter.
Perhaps the simplest type of arbitration scheme is fixed priority, where each type of request in a system is assigned a fixed priority. When an arbiter receives multiple requests, the request with the highest priority always receives access to the data bus. For example, if there is a request A of high priority and request B of medium priority, then request B will receive memory access only if request A is not present.
A major problem with fixed priority arbitration schemes is that they can handle only a limited number of requesters because of the risk that devices with a low priority will not be timely serviced, if at all. For example, in a fixed priority scheme, if there is a request A of high priority, request B of medium priority, and request C of low priority, and the arbiter is constantly bombarded with requests A and B, then request C will xe2x80x9cstarvexe2x80x9d and never be serviced. The risk of starvation rises with the number of devices that request service. In fact, if a fixed priority scheme includes ten devices with ten levels of priority, starvation is virtually guaranteed.
Another type of arbitration scheme used in the prior art is a round robin scheme. The standard round robin scheme deals with all the requests in a fixed order. For example, if request A is of high priority, request B of medium priority, and request C of low priority, the round robin scheme will grant request A first, then grant request B, and then grant request C. However, if request A is not present, then request B becomes of high priority, request C of medium priority and request A of low priority. Therefore, the round robin scheme continually shifts priority between all of the devices it services.
As with the fixed priority scheme, round robin schemes also run into starvation problems when handling a large number of requesters. Take the example of a round robin scheme that looks for and grants requests A-Z in alphabetical order, where request A has not been asserted at the time it is sought. If request A is asserted at the time that request B is being sought, then it is possible that request A will not be granted until requests B-Z have been serviced.
Another type of arbitration scheme used in the prior art is a dynamic priority scheme, which utilizes a set of rules that determine the priority of the requestors established by the arbiter. For example, the rules may give a higher priority to requesters that require the most bandwidth of memory access from a SDRAM or give higher priority to requestors that have most recently been serviced.
Dynamic priority schemes allow for in theory, an unlimited number of ways for an arbiter to establish the priority of multiple requestors. However, the more complicated the rules are, the more process overhead will be required to maintain the dynamic priority scheme. This is particularly true in cases where the dynamic priority scheme must arbitrate between real time devices.
There are several other arbitration schemes in the prior art such as a window based scheme that gives each requestors a certain slice of time where memory access will be granted. The advantage of the window based scheme is that it can guarantee bandwidth for its requesters. However, as with the dynamic priority scheme, the windows based scheme involving multiple requestors would be very complicated and require a great deal of logic. Furthermore, a window based scheme would have difficulty maintaining efficient data bus utilization because a slice in time may be set aside for a device when there is no request resulting in idle tine where the bus does nothing.
In view of the foregoing, it is desirable to have methods and an apparatus that is able to establish priority between multiple devices with real time requirements, while at the same time maintaining efficient utilization of the data bus.
The present invention fills these needs by providing methods and an apparatus for arbitrating between and servicing requestors having real time requirements while maintaining efficient utilization of the data bus. It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device or a method. Several inventive embodiments of the present invention are described below.
In one embodiment of the present invention, a data bus arbitration system is disclosed. The data bus arbitration system includes a bus status monitor which is coupled to a data bus and generates a bus status signal for use by an arbiter. The arbiter is coupled to number of requesters, each of which belong to a distinct class of requesters. The arbiter arbitrates between multiple requests using heuristics dependent upon the classes of the requesters. The arbiter grants access to one of the requestors to the data bus while maintaining an efficiency of at least 80% of a total data bandwidth of the data bus for all requesters. One of the distinct classes of requesters is preferably a real time class. The data bus arbitration system preferably includes a timer that provides an indication of when access to the data bus must be granted for a real time request.
In another embodiment of the present invention, a method for data bus arbitration is disclosed. The method includes monitoring a status of a data bus. A data bus request from a requestor belonging to a first class of requesters is first processed by a first heuristic method. The method then proceeds with second processing a data bus request from a requestor belonging to a second class of requestors by a second heuristic method. Access to the data bus is granted to a requestor based upon the status of the data bus, the first processing and the second processing, understanding that the first class of requestors is of a generally higher priority than the second class of requestors. The method preferably includes third processing a data bus request from a requester belonging to a third class of requesters by a third heuristic method, understanding that the second class of requesters is of a generally higher priority than the third class of requestors.
In yet another embodiment of the present invention, a method for data bus arbitration is disclosed. The method includes means for monitoring a status of a data bus. A data bus request from a requester belonging to a first class of requesters is processed by a first processing means using a first heuristic method. The method then proceeds with processing a data bus request using a second processing means from a requester belonging to a second class of requesters by a second heuristic method. Access to the data bus is granted to a requestor based upon the status of the data bus, the first processing means and the second processing means, understanding that the first class of requestors is of a generally higher priority than the second class of requestors.
An advantage of the present invention is that it provides for arbitrating between and granting requestors having real time requirements while preventing starvation of all devices in need of service. The arbiter of the present invention is able to grant priority based not only on the type of request received, but also based on the requirements of the request. Furthermore, the present invention maintains efficient utilization of the data bus.
Other aspects and advantages of the invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.